package sum_of_three_numbers

import (
	"fmt"
)

//ThreeSum 三数之和等于0
func ThreeSum(nums []int) [][]int{
	ln := len(nums)
	if ln < 3 {
		return nil
	}
	nums = shellSort(nums)
	results := make(map[string][]int, 1)
	for  i := 1; i < ln -1; i++ {
		l := 0
		r := ln -1
		for l <i && r > i {
			key := getkey([]int{nums[l], nums[]})
			sum := nums[l] + nums[i] + nums[r]
			if sum == 0 {
				sorted := shellSort([]int{nums[l], nums[i], nums[r]})
				results[fmt.Sprintf("%d%d%d", sorted[0], sorted[1], sorted[2])] = sorted
				l++
				r--
				continue
			}
			if sum < 0 {
				if l +1 == i {
					r--
				} else{
					l++
				}
			}
			if sum > 0 {
				if r - 1 == i {
					l++
				} else {
					r--
				}
			}
		}
	}
	rets := [][]int{}
	for _, v := range results {
		rets = append(rets, v)
	}
	return rets
}

func shellSort(nums []int) []int {
	ln := len(nums)
	if ln < 2 {
		return nums
	}
	for gap := ln/2; gap > 0; gap /= 2 {
		for n := 0; n < ln; n++ {
			for m := n+gap; m < ln; m += gap {
				for k := m; k > n; k -= gap {
					if nums[k-gap] > nums[k] {
						nums[k-gap], nums[k] = nums[k], nums[k-gap]
					}
				}
			}
		}
	}
	return nums
}

func getmaps(nums []int) map[int][]int {
	nums = shellSort(nums)
	return fmt.Sprintf("%d%d%d", nums[0], nums[1], nums[2])
}